#include <queue> // 使用队列

#include <iostream>

using namespace std;

template <class T>
struct Node
{
   T data;
   Node *left;
   Node *right;
};


class solution {

    public:
    // 用于打印二叉树,参数是二叉树的根结点
    void print(Node<int> * root){

        // 如果根结点是空的话，直接退出
        if(root == NULL){
            return;
        }

        queue< Node<int> * > q;

        q.push(root);

        // 当队列不为空时执行
        while(!q.empty()){

            Node<int> *node = q.front(); // 获得队首元素

            q.pop(); //出队

            cout << node->data << " ";  // 打印结点的值

            // 先后向队列中添加左右结点
            if(node->left != NULL){
                q.push(node->left);
            }

            if(node->data != NULL){
                q.push(node->right);
            }

        }

        cout << endl;
        return;
    }
};